package cn.orange.ch01_array.binarysearch;

/**
 * LC35.搜索插入位置
 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 请必须使用时间复杂度为 O(log n) 的算法
 */
public class LC35 {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        /*
        循环结束条件为left == right，因此循环结束前mid = left
        若此时target > nums[mid]，则插入位置为mid + 1，且会执行left = mid + 1因此插入位置最终返回left
        若此时target < nums[mid]，则插入位置为mid，且此时直到循环结束都是left = mid因此插入位置最终返回left
        闭区间的二分法寻找插入位置分析过程相同
         */
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                return mid;
            }
        }
        return left;
    }
    public static void main(String[] args) {
        LC35 alg = new LC35();
        System.out.println(alg.searchInsert(new int[]{1, 3, 5, 6}, 5));
        System.out.println(alg.searchInsert(new int[]{1, 3, 5, 6}, 2));
        System.out.println(alg.searchInsert(new int[]{1, 3, 5, 6}, 7));
    }
}
